package main

type ListNode struct {
	Val  int
	Next *ListNode
}

type Heap []*ListNode

func Init(h *Heap) {
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

func Push(h *Heap, x interface{}) {
	h.Push(x)
	up(h, h.Len()-1)
}

func Pop(h *Heap) interface{} {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

func up(h *Heap, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h *Heap, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(*ListNode))
}

func (h *Heap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func mergeKLists(lists []*ListNode) *ListNode {
	head := &ListNode{}
	node := head
	var h Heap = []*ListNode{}
	Init(&h)
	for _, l := range lists {
		if l != nil {
			Push(&h, l)
		}
	}
	for h.Len() > 0 {
		n2 := Pop(&h).(*ListNode)
		node.Next = &ListNode{
			Val:  n2.Val,
			Next: nil,
		}
		node = node.Next
		if n2.Next != nil {
			Push(&h, n2.Next)
		}
	}
	return head.Next
}

func main() {

}
